package com.lx.algorithm.recursion.class19;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-18 15:55:56
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-18     张李鑫                     1.0         1.0 Version
 */
public class ConvertToLetterString {
    /**
     * 规定1和A对应、2和B对应、3和C对应...26和Z对应
     * 那么一个数字字符串比如"111”就可以转化为:
     * "AAA"、"KA"和"AK"
     * 给定一个只有数字字符组成的字符串str，返回有多少种转化结果
     */

    public static int number(String str) {
        if (str == null || str.isEmpty()) {
            return 0;
        }
        return process(str.toCharArray(), 0);
    }

    private static int process(char[] str, int i) {
        //如果能走到说明有一种转换结果
        if (i == str.length) {
            return 1;
        }
        if (str[i] == 48) {
            return 0;
        }

        int p1 = process(str, i + 1);
        if (i + 1 < str.length && (str[i] - '0') * 10 + (str[i + 1] - '0') < 27) {
            p1 += process(str, i + 2);
        }
        return p1;
    }


    // 为了测试
    public static String randomString(int len) {
        char[] str = new char[len];
        for (int i = 0; i < len; i++) {
            str[i] = (char) ((int) (Math.random() * 10) + '0');
        }
        return String.valueOf(str);
    }

    /**
     * 从右到左的动态规划
     *
     * @param string
     * @return
     */
    public static int dp(String string) {
        if (string == null || string.isEmpty()) {
            return 0;
        }

        char[] str = string.toCharArray();
        int[] dp = new int[str.length + 1];
        dp[str.length] = 1;
        for (int i = str.length - 1; i >= 0; i--) {
            if (str[i] == 48) {
                dp[i] = 0;
                continue;
            }
            int p1 = dp[i + 1];
            if (i + 1 < str.length && (str[i] - '0') * 10 + (str[i + 1] - '0') < 27) {
                p1 += dp[i + 2];
            }
            dp[i] = p1;
        }
        return dp[0];
    }


    /**
     * 从左边到右边的尝试
     * @param str
     * @return
     */
    public static int dpII(char[] str) {
        if (str == null || str.length == 0 || str[0] == '0') {
            return 0;
        }
        int[] dp = new int[str.length + 1];
        dp[0] = 1;
        for (int i = 1; i < str.length; i++) {
            if (str[i] == '0') {
                if (str[i - 1] == '0' || (str[i - 1] - '0') * 10 + (str[i] - '0') > 27) {
                    return 0;
                }
                dp[i] = i - 2 >= 0 ? dp[i - 2] : 1;
            } else {
                dp[i] = dp[i - 1];
                if (str[i - 1] != '0' && (str[i - 1] - '0') * 10 + (str[i] - '0') < 27) {
                    dp[i] += i - 2 >= 0 ? dp[i - 2] : 1;
                }
            }
        }
        return dp[str.length - 1];
    }


    public static void main(String[] args) {
        int N = 30;
        int testTime = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int len = (int) (Math.random() * N);
            String s = randomString(len);
            int number = dpII(s.toCharArray());
            int dp = dp(s);
            if (dp != number) {
                System.out.println(s);
                System.out.println(dp);
                System.out.println(number);
                break;
            }
        }
    }

}
